The basic idea in this section should be attributed to Thomas Dullien who discussed the possibility of using Gröbner bases to find differential characteristics with the author in November 2008 in a coffee shop in London. This chapter forms the key idea of the paper ``Algebriac Precomputations in Differential and Integral cryptanalysis'' by Carlos Cid, Thomas Dullien, Jean-Charles Faugère, Ludovic Perret and the author published at INSCRYPT 2010 \cite{acdfp:inscrypt2010}.

\section{Ideal Membership as Implication}

The main idea involves shifting the emphasis of previous algebraic attacks away from attempting to solve an
equation system towards \textit{using ideal membership as implication}. In others words, instead of trying to solve an equation system arising from the cipher, we use Gr\"obner basis methods to calculate what a particular input/output pattern \emph{implies}. 

To explain the main idea we start with a small example. Consider the 4-bit S-Box of \PRESENT~\cite{present}.\footnote{S-Boxes were studied using algebraic techniques before, cf.\ \cite{SK98,ars:thesis2005}.}
$$
S = (12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2).
$$
The S-Box can be completely described by a set of polynomials that express each output bit in terms of the input bits.  One can consider a \emph{pair} of input bits $X'_{1,0},\dots,X'_{1,3}$ and $X''_{1,0},\dots,X''_{1,3}$ and their respective output bits $Y'_{1,0},\dots,Y'_{1,3}$ and $Y''_{1,0},\dots,Y''_{1,3}$. Since the output bits are described as polynomials in the input bits, it is easy to build a set of polynomials describing the parallel application of the S-Box to the pair of input bits. Assume the fixed input difference of $(0,0,0,1)$ holds for this S-Box. This can be described algebraically by adding the polynomials $X'_{1,3} + X''_{1,3} = 1$, $X'_{1,j}+X''_{1,j}=0$ for $0 \leq j < 3$ to the set. As usual and in all calculations performed in this thesis, the field equations are also added. 

The set of equations now forms a description of the parallel application of the S-Box to two inputs with a fixed input difference. The ideal \(I\) spanned by these polynomials contains \emph{all} polynomials that are \emph{implied} by the set.  If all equations in the generating set of the ideal evaluate to zero, it is clear that any element of \(I\) evaluates to zero. This means that \emph{any equation in the ideal will always vanish} if it is assigned values generated by applying the S-Box to a pair of inputs with the above-mentioned input difference. 

From a cryptographic point of view, it is important to understand what relations between output bits will hold for a particular  input difference. As a consequence, we are looking for polynomials in \emph{just the output bits} which are contained in \(I\).  Algebraically, we are trying to find elements of the ideal 
$
I_Y = I \bigcap \F_2[Y'_{1,0},\dots,Y'_{1,3},Y''_{1,0},\dots,Y''_{1,3}]
$
where \(I\) is the ideal spanned by our original polynomials. A \emph{deglex} Gr\"obner basis $G_Y$ of this ideal can be computed using standard elimination techniques \cite[p.168]{Becker1991}. For this, we can set up a block or product ordering where all output variables are lexicographically smaller than any other variable in the system. In addition, we fix the \emph{deglex} ordering among the output variables. Computing the Gröbner basis with respect to such an ordering gives us the Gröbner basis $G_Y$. We note that $G_Y$ will contain the relations of lowest degree of $I_Y$ due to the choice of monomial ordering. In our example we have: 

\begin{eqnarray*}
    G_Y &=& [ Y'_{1,3} + Y''_{1,3} + 1,\\
&& Y'_{1,0} + Y'_{1,2} + Y''_{1,0} + Y''_{1,2} + 1,\\
&& Y''_{1,0} Y''_{1,2} + Y'_{1,2} + Y''_{1,0} + Y''_{1,1} + Y''_{1,3},\\
&& Y''_{1,0} Y''_{1,1} + Y''_{1,0} Y''_{1,3} + Y''_{1,1} Y''_{1,2} + Y''_{1,2} Y''_{1,3} + Y'_{1,1} + Y''_{1,0} + Y''_{1,1},\\
&& Y'_{1,2} Y''_{1,2} + Y''_{1,1} Y''_{1,2} + Y''_{1,2} Y''_{1,3},\\
&& Y'_{1,2} Y''_{1,0} + Y''_{1,1} Y''_{1,2} + Y''_{1,2} Y''_{1,3} + Y'_{1,1} + Y'_{1,2} + Y''_{1,0} + Y''_{1,3},\\
&& Y'_{1,1} Y''_{1,2} + Y'_{1,2} Y''_{1,1} + Y'_{1,2} Y''_{1,3} + Y''_{1,1} Y''_{1,2} + Y'_{1,1} + Y'_{1,2} + Y''_{1,1},\\
&& Y'_{1,1} Y''_{1,1} + Y'_{1,1} Y''_{1,3} + Y''_{1,1} Y''_{1,2} + Y''_{1,1} Y''_{1,3} + Y''_{1,2} Y''_{1,3} + Y''_{1,1},\\
&& Y'_{1,1} Y''_{1,0} + Y'_{1,2} Y''_{1,1} + Y'_{1,2} Y''_{1,3} + Y''_{1,0} Y''_{1,3} + Y''_{1,1} Y''_{1,2} + Y''_{1,2} Y''_{1,3} + Y'_{1,1} + Y''_{1,3},\\
&& Y'_{1,1} Y'_{1,2} + Y'_{1,2} Y''_{1,3} + Y''_{1,1} Y''_{1,2} + Y''_{1,2} Y''_{1,3} + Y'_{1,2}].\\
\end{eqnarray*}

There is no other linear or quadratic polynomial $p \in I_Y$ which is not a simple algebraic combination of the polynomials in $G_Y$. 

Of course, we can ask different questions instead of looking for low degree equations. For instance, we can query whether there are equations in the bits $Y'_{1,3}, Y''_{1,2},Y''_{1,3}$ induced by the input difference by setting up the appropriate monomial ordering.

In order to formalise this idea, consider a function $E$ (for example a block cipher).\footnote{If we consider block ciphers instead of S-boxes then keys are involved. However, from an algebraic perspective, these merely represent more independent variables.} Assume that $E$ can be expressed as a set of algebraic equations $F$ over a finite field $\F$. If one application of the function can be described as a set of equations, \(d\) parallel applications to \(d\) different inputs (which we denote \(P_0, \dots, P_{d-1}\)) can also be described as a set of equations. We call the set of equations  relating the \(i\)-th input and output \(E_i\) and the matching polynomial system \(F_i\). The outputs of these equations are called \(C_0, \dots, C_{d-1}\). Furthermore, assume some property $\Lambda$ holding on $P_0, \dots, P_{d-1}$ which can be expressed by a set of algebraic equations $F_\Lambda$. A natural question to ask is: How do properties on \(P_0, \dots, P_{d-1}\) affect properties on \(C_0, \dots, C_{d-1}\) ? 
We combine the sets of polynomials $\overline{F} = F_\Lambda \cup (\bigcup_{i=0}^{d-1} F_i)$ and consider the ideal \(I = \ideal{\overline{F}}\) spanned by \(\overline{F}\). Next, we compute the unique reduced Gr\"obner basis \(G_C\) of the ideal $I_{C} = I \cap \F[C_0,\dots,C_{d-1}]$. Now $G_C$ contains all ``relevant'' polynomials in $C_0,\dots,C_{d-1}$, where ``relevant'' is determined by the monomial ordering.

As soon as we can compute the Gröbner basis $G_C$ for the function $E$ then we only need to collect the right polynomials from $G_C$. However, for many functions $E$ computing $G_C$ seems infeasible using current Gröbner basis techniques, implementations and computing power. Thus we have to relax some conditions hoping that we still can recover some equations using a similar technique. We provide below  a few heuristics and techniques which still allow recovering \emph{some} relevant equations. 

\begin{description}
 \item[Early Abort.]  To recover some properties we might not need to compute the complete Gr\"obner basis, instead we may opt to stop the computation at some degree \(D\). 


\item[Replacing Symbols by Constants.] It is possible to replace the symbols $P_0$, $\dots$, $P_{d-1}$ by some constants satisfying the constraint $\Lambda$ which further simplifies the computation. Of course any polynomial recovered from such a computation would have to be checked against other values to verify that it actually holds in general or with high probability.

\item[Choosing a Different Monomial Ordering.] Instead of computing with respect to an elimination ordering, which is usually more expensive than a degree compatible ordering, we may choose to perform our computions with respect to  an easier ordering such as \emph{degrevlex}. 
Used together with {\bf Early Abort},  we have no assurances about the uniqueness and completeness of the recovered system. However, we might still be able to recover some information.

\item[Computing Normal Forms Only.] We can also compute equations by computing normal forms only. For many ciphers it is possible to construct a Gröbner basis for the round transformation \cite{Buchmann2006,bulgin-brickenstein:eprint2008} with respect to some elimination ordering without any polynomial reductions. These constructions exploit the fact that a system of polynomials is a Gröbner basis if each polynomial has a leading term which is pairwise prime with every other leading term (cf.\ Definition~\ref{def:buchberger_first_criterion}).  Using this property, we may construct a Gröbner basis for some elimination ordering for the inverse of the cipher, i.e. the decryption process, such that the input variables are lexicographically bigger than the output variables of some round. Furthermore, we construct the monomial ordering such that the variables of round $i-1$ are lexicographically bigger than the variables for round $i$. Furthermore, the symbols $C_i$ are the lexicographically smallest. 
 
If $G'$ is such a Gröbner basis for $r$ rounds for the first encryption and $G''$ such a Gröbner basis for $r$ rounds for the second encryption, we can combine these bases to $G = G' \cup G''$ which still is a Gröbner basis. Now we can compute the normal form of $X'_i + X''_i + \Delta X_i$ with respect to $G$. This will eliminate all variables $> C_i$ as much as possible by construction. If this computation does not give equations in the $C_i$ only, we may opt to perform an interreduction on several such equations hoping that this way the remaining unwanted variables are eliminated. For example, such a Gröbner basis for one application of the \PRESENT S-Box is

\begin{align*}
X_{1,0} & + Y_{1,0}Y_{1,1}Y_{1,3} + Y_{1,1}Y_{1,2}Y_{1,3} + Y_{1,2}Y_{1,3} + Y_{1,0} + Y_{1,1} + Y_{1,2} + Y_{1,3},\\
X_{1,1} &+ Y_{1,0}Y_{1,1}Y_{1,3} + Y_{1,0}Y_{1,2}Y_{1,3} + Y_{1,1}Y_{1,2}Y_{1,3} + Y_{1,0}Y_{1,2} + Y_{1,0}Y_{1,3} \\
  & + Y_{1,1}Y_{1,2} + Y_{1,1}Y_{1,3} + Y_{1,2}Y_{1,3} + Y_{1,0} + 1,\\
X_{1,2} &+ Y_{1,0}Y_{1,1}Y_{1,3} + Y_{1,0}Y_{1,2}Y_{1,3} + Y_{1,1}Y_{1,2}Y_{1,3} + Y_{1,0}Y_{1,1} + Y_{1,0}Y_{1,2} \\
 & + Y_{1,1}Y_{1,3} + Y_{1,0} + Y_{1,2} + Y_{1,3},\\
X_{1,3} &+ Y_{1,0}Y_{1,2} + Y_{1,1} + Y_{1,3} + 1\\
\end{align*}
The normal form of the equation $X'_{1,3} + X''_{1,3} + 1$ with respect to $G$ (i.e. two of such systems for $X',Y'$ and $X'',Y''$)  is $Y'_{1,0}Y'_{1,2} + Y''_{1,0}Y''_{1,2} + Y'_{1,1} + Y'_{1,3} + Y''_{1,1} + Y''_{1,3} + 1.$
\end{description}

\vspace{1cm}

These techniques have a variety of applications in block cipher cryptanalysis as we will show in the following chapters.
